"""
交换单链表里两个链点
    在这个实验中，我们要给定两个值，
    如果这两个值都在单链表的链点中，
    即交换这两个链点在单链表的位置。
    举例：
        1->2->3->4->5
        input:1 4 output:4->2->3->1->5
    目标：交换两个链点在链表中的位置
        不改变其他链点在链表中的位置
"""


class Node:
    def __init__(self, data: object, node: object):
        self.data = data
        self.next = node


class Chain:
    def __init__(self):
        self.head = Node(data=None, node=None)
        self.tail = self.head

    def insert(self, data: object, previous: Node) -> None:
        node = Node(data=data, node=previous.next)
        previous.next = node
        while node.next != None:
            node = node.next
        self.tail = node

    def extend(self, data: object) -> None:
        self.insert(data=data, previous=self.tail)

    def delete(self, data: object) -> bool:
        current = self.head
        while current.next != None:
            if current.next.data == data:
                break
            current = current.next
        if current.next == None:
            return False
        node = current.next
        current.next = node.next
        while current.next != None:
            current = current.next
        self.tail = current
        return True

    def swap(self, data1: object, data2: object) -> bool:
        node = self.head
        while node.next != None:
            if node.next.data == data1:
                node1_ = node
                node1 = node.next
            if node.next.data == data2:
                node2_ = node
                node2 = node.next
            node = node.next
        if "node1" in locals() and "node2" in locals():
            node1.next, node2.next = node2.next, node1.next
            node1_.next, node2_.next = node2, node1
            return True
        return False

    def browse(self) -> None:
        node = self.head
        while node.next != None:
            node = node.next
            print(node.data, end=" ")
        print("\n")


chain = Chain()
for i in range(5):
    chain.extend(i)
chain.browse()
chain.swap(1, 4)
chain.browse()
